package practice.tmp;

public class Solution215 {
    public int findKthLargest(int[] nums, int k) {
        int i = 0;
        int j = nums.length - 1;
        while (true) {
            int index = quickSort(nums, i, j);
            if (index == nums.length - k) return nums[index];
            else if (index < nums.length - k) i = index + 1;
            else j = index - 1;
        }
    }

    public int quickSort(int[] nums, int left, int right) {
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && nums[j] >= nums[left]) j--;
            while (i < j && nums[i] <= nums[left]) i++;
            swap(nums, i, j);
        }
        swap(nums, left, i);
        return i;
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
